package com.rayboo.example.algorithm.sort;

import com.rayboo.example.util.ArrayUtils;

import java.util.Arrays;

/**
 * 冒泡排序
 *
 * @author ray
 * @since 2019/08/01
 *
 * <p>原理：比较两个相邻的元素，将值大的元素交换至右端。
 *
 * <p>思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。
 * 然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。
 *
 * <p>https://cloud.tencent.com/developer/article/1473170
 * <p>https://www.runoob.com/w3cnote/bubble-sort.html
 */
public class BubbleSort {

    public static void main(String[] args) {
        int arr[] = ArrayUtils.randomNoRepeatIntArray(0, 100, 20);
        System.out.println("排序前：\n" + Arrays.toString(arr));

        bubbleSort(arr);
        System.out.println("排序后：\n" + Arrays.toString(arr));

        System.out.println("==============================");
        int[] ints = ArrayUtils.randomRepeatIntArray(0, 100, 5);
        System.out.println("排序前：\n" + Arrays.toString(ints));
        bubbleSortOptimize(ints);
        System.out.println("排序后(优化)：\n" + Arrays.toString(ints));

        System.out.println("==============================");
        int[] array = ArrayUtils.randomRepeatIntArray(0, 100, 5);
        System.out.println("排序前：\n" + Arrays.toString(array));
        bubbleSortDesc(array);
        System.out.println("排序后(DESC)：\n" + Arrays.toString(array));

    }

    /**
     * 冒泡排序
     *
     * @param sourceArray 数组
     * @return 排序后的数组
     * @throws Exception 异常
     */
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        for (int i = 1; i < arr.length; i++) {
            // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
            boolean flag = true;

            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;

                    flag = false;
                }
            }

            if (flag) {
                break;
            }
        }
        return arr;
    }

    /**
     * 冒泡排序（正序）
     *
     * @param arr 数组
     */
    public static void bubbleSort(int[] arr) {
        // 外循环控制排序的趟数
        for (int i = 0; i < arr.length; i++) {
            // 内循环控制每一趟排序多少次
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 冒泡排序（优化）
     *
     * @param arr 数组
     */
    public static void bubbleSortOptimize(int[] arr) {
        // 用来交换的临时数
        int temp = 0;
        // 交换标识
        boolean flag = false;

        // 遍历的次数
        for (int i = 0; i < arr.length - 1; i++) {
            flag = false;
            // 从后向前依次比较相邻的两个数大小，遍历一次后，把数组中第i小的数放在第i个位置上
            for (int j = arr.length - 1; j > i; j--) {
                // 比较相邻的数，如果前面的大于后面的数，则交换
                if (arr[j - 1] > arr[j]) {
                    temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                    flag = true;
                }
            }
            // 如果flag为false，说明本轮遍历没有交换，已经是有序数组，结束循环
            if (!flag) break;
        }
    }

    /**
     * 冒泡排序（倒序）
     *
     * @param arr 数组
     */
    public static void bubbleSortDesc(int[] arr) {
        int length = arr.length;
        if (length > 0) {
            for (int i = length - 1; i > 0; i--) {
                for (int j = length - 1; j > length - 1 - i; j--) {
                    if (arr[j] > arr[j - 1]) {
                        int temp = arr[j];
                        arr[j] = arr[j - 1];
                        arr[j - 1] = temp;
                    }
                }
            }
        }
    }
}
